package nfa_generator;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import ast_generator.ASTNode;
import ast_generator.ASTTree;

/**
 * Generates and NFAGraph from a list of ASTTrees for a given language.
 * Takes in a list of ASTTrees, generates NFAGraphs for each tree, then 
 * joins them with an initial state and epsilon transitions.
 * The final graph that is returned contains a list of end states instead of a single end state.
 * 
 * @author Joshua
 *
 */
public class NFAGenerator {
	private List<ASTTree> astTreeList;
	private List<NFAGraph> nfaList;
	private NFAGraph finalGraph;
	
	/**
	 * Constructor for NFAGenerator, takes in a list of ASTTrees.
	 * 
	 * @param astTreeList - List of ASTTrees to generate NFA from.
	 */
	public NFAGenerator(List<ASTTree> astTreeList) {
		
		this.astTreeList = astTreeList;
		nfaList = new ArrayList<NFAGraph>();
		finalGraph = null;
		
	}
	
	/**
	 * Constructs an NFA graph for the language from the given AST trees.
	 * 
	 * @return NFAGraph - endState is null, has a list finalEndStates
	 */
	public NFAGraph generateNFA() {
		
		for(ASTTree tree : astTreeList) {
			nfaList.add(traversal(tree.getRoot(), tree.getTokenType(), null));
		}
				
		finalGraph = new NFAGraph(new NFANode());
		for(NFAGraph graph : nfaList) {
			finalGraph.getStartState().addTransition(Arrays.asList("epsilon"), graph.getStartState());
			finalGraph.addStates(graph.getStates());
			finalGraph.addFinalEndState(graph.getEndState());
		}
		
		int n = 0;
		for(NFANode node : finalGraph.getStates()) {
			node.setName("" + n);
			n++;
		}
		return finalGraph;
	}
	
	/**
	 * Recursive post-order traverses the ASTTree, building the NFA graph to accept
	 * the given language for a token.
	 * 
	 * @param astNode - Root node or node currently being examined.
	 * @param tokenType - String for token that the tree defines.
	 * @param graph - NFAGraph that is being built.
	 * 
	 * @return  root - NFAGraph, the final graph for the tree or what has been built so far. 
	 */
	public NFAGraph traversal(ASTNode astNode, String tokenType, NFAGraph graph) {
		NFAGraph left = null;
		NFAGraph right = null;
		NFAGraph root = null;

		//Check if node is null, doesn't exist.
		if(astNode == null || astNode.getValue() == null) {
			return null;
		}
		
		//Post order traversal
		left = traversal(astNode.getLeft(), tokenType, graph);
		right = traversal(astNode.getRight(), tokenType, graph);
		
		//If children are null
		if(left == null && right == null) {
			//Current node is input
			if(astNode.isInput()) {
				root = getPrimitiveGraph(astNode.getValue(), tokenType);
			}
			//Current node is operation
			else if(astNode.isOperation()) {
				return null;
			}
		}
		//If children are not null and current node is an operation
		else if(left != null && right != null && astNode.isOperation()) {
			if(astNode.getValue().get(0).compareTo("concat") == 0) {
				root = operatorConcatenation(left, right);
			}
			else if(astNode.getValue().get(0).compareTo("|") == 0) {
				root = operatorAlternation(left, right);
			}
		}
		//Left child is not null, right child is null, current node is an operation
		else if(left != null && right == null && astNode.isOperation()) {
			if(astNode.getValue().get(0).compareTo("*") == 0) {
				root = operatorReplication(left);
			}
			else if(astNode.getValue().get(0).compareTo("+") == 0) {
				root = operatorReplicationPlus(left);
			}
			else if(astNode.getValue().get(0).compareTo("?") == 0) {
				root = operatorQuestionMark(left);
			}
			else if(astNode.getValue().get(0).compareTo("|") == 0) {
				root = left;
			}
			else if(astNode.getValue().get(0).compareTo("concat") == 0) {
				root = left;
			}
		}
		//Left child is null, right child is not null, current node is an operation
		else if(left == null && right != null && astNode.isOperation()) {
			if(astNode.getValue().get(0).compareTo("*") == 0) {
				root = operatorReplication(right);
			}
			else if(astNode.getValue().get(0).compareTo("+") == 0) {
				root = operatorReplicationPlus(right);
			}
			else if(astNode.getValue().get(0).compareTo("?") == 0) {
				root = operatorQuestionMark(right);
			}
			else if(astNode.getValue().get(0).compareTo("|") == 0) {
				root = right;
			}
			else if(astNode.getValue().get(0).compareTo("concat") == 0) {
				root = right;
			}
		}
		//Return root graph
		return root;
	}
	
	/**
	 * Builds a primitive, two-node graph for a given input and returns it.
	 * 
	 * @param input - The String value to transition on.
	 * 
	 * @return newGraph - NFAGraph, new primitive NFAGraph
	 */
	public NFAGraph getPrimitiveGraph(List<String> input, String token) {
		NFANode startState = new NFANode();
		NFANode endState = new NFANode();
		startState.addTransition(input, endState);
		endState.setToken(token);
		NFAGraph newGraph = new NFAGraph(startState, endState);
		return newGraph;
	}
	
	/**
	 * Takes in two graphs, concatenates them using an epsilon transition, and returns the new graph.
	 * 
	 * @param g1 - NFAGraph to add g2 to.
	 * @param g2 - NFAGraph to add to g1.
	 * 
	 * @return newGraph - NFAGraph that is concatenation of g1 and g2 with "epsilon" transition.
	 */
	public NFAGraph operatorConcatenation(NFAGraph g1, NFAGraph g2) {
		g1.getEndState().addTransition(Arrays.asList("epsilon"), g2.getStartState());
		g1.getEndState().setToken(null);
		NFAGraph newGraph = new NFAGraph();
		newGraph.setStartState(g1.getStartState());
		newGraph.setEndState(g2.getEndState());
		newGraph.addStates(g1.getStates());
		newGraph.addStates(g2.getStates());
		return newGraph;
	}
	
	/**
	 * Takes in two graphs, ORs them using epsilon transitions, and returns the new graph.
	 * 
	 * @param g1 - NFAGraph to OR with g2
	 * @param g2 - NFAGraph to OR with g1
	 * 
	 * @return newGraph - NFAGraph that is the alternation of g1 and g2 with epsilon transitions.
	 */
	public NFAGraph operatorAlternation(NFAGraph g1, NFAGraph g2) {
		NFANode startState = new NFANode();
		NFANode endState = new NFANode();
		startState.addTransition(Arrays.asList("epsilon"), g1.getStartState());
		startState.addTransition(Arrays.asList("epsilon"), g2.getStartState());
		
		g1.getEndState().addTransition(Arrays.asList("epsilon"), endState);
		g2.getEndState().addTransition(Arrays.asList("epsilon"), endState);
		
		endState.setToken(g2.getEndState().getToken());
		g1.getEndState().setToken(null);
		g2.getEndState().setToken(null);
		

		NFAGraph newGraph = new NFAGraph(startState, endState);
		newGraph.addStates(g1.getStates());
		newGraph.addStates(g2.getStates());
		return newGraph;
	}
	
	/**
	 * Takes in a graph, applies the replication, or Kleene Enclosure, operator using epsilon transitions, and returns the new graph.
	 * 
	 * @param g1 - NFAGraph to apply replication to.
	 * 
	 * @return newGraph - NFAGraph that contains the replication of g1.
	 */
	public NFAGraph operatorReplication(NFAGraph g1) {
		NFANode startState = new NFANode();
		NFANode endState = new NFANode();
		startState.addTransition(Arrays.asList("epsilon"), g1.getStartState());
		g1.getEndState().addTransition(Arrays.asList("epsilon"), endState);
		endState.setToken(g1.getEndState().getToken());
		g1.getEndState().setToken(null);
		startState.addTransition(Arrays.asList("epsilon"), endState);
		g1.getEndState().addTransition(Arrays.asList("epsilon"), g1.getStartState());
		NFAGraph newGraph = new NFAGraph(startState, endState);
		newGraph.addStates(g1.getStates());
		return newGraph;
	}
	
	/**
	 * Takes in a graph, applies the one or more replication operator using epsilon transitions, and returns the new graph.
	 * 
	 * @param g1 - NFAGraph to apply one or more replication to.
	 * 
	 * @return newGraph - NFAGraph that contains the one or more replication of g1.
	 */
	public NFAGraph operatorReplicationPlus(NFAGraph g1) {
		NFANode startState = new NFANode();
		NFANode endState = new NFANode();
		startState.addTransition(Arrays.asList("epsilon"), g1.getStartState());
		g1.getEndState().addTransition(Arrays.asList("epsilon"), endState);
		g1.getEndState().addTransition(Arrays.asList("epsilon"), g1.getStartState());
		endState.setToken(g1.getEndState().getToken());
		g1.getEndState().setToken(null);
		NFAGraph newGraph = new NFAGraph(startState, endState);
		newGraph.addStates(g1.getStates());
		return newGraph;
	}
	
	/**
	 * Takes in a graph, applies the zero or one operator using epsilon transitions, and returns the new graph.
	 * 
	 * @param g1 - NFAGraph to apply the zero or one operation to.
	 * 
	 * @return newGraph - NFAGraph that contains the zero or one operation of g1.
	 */
	public NFAGraph operatorQuestionMark(NFAGraph g1) {
		NFANode startState = new NFANode();
		NFANode endState = new NFANode();
		startState.addTransition(Arrays.asList("epsilon"), g1.getStartState());
		g1.getEndState().addTransition(Arrays.asList("epsilon"), endState);
		startState.addTransition(Arrays.asList("epsilon"), endState);
		endState.setToken(g1.getEndState().getToken());
		g1.getEndState().setToken(null);
		NFAGraph newGraph = new NFAGraph(startState, endState);
		newGraph.addStates(g1.getStates());
		return newGraph;
	}	
}